import time
numQueue = []
resultStack = []
checkPoint = []

SIZE = 4

board = [[0 for r in range(SIZE)] for c in range(SIZE)]

def GetIndexFromRowCol(r, c):
    return r * SIZE + c

def GetRowColFromIndex(idx):
    r = int(idx / SIZE)
    c = int(idx % SIZE)
    return r, c

def InitNumQueue():
    global numQueue
    numQueue = []
    for i in range(1, SIZE * SIZE + 1):
        numQueue.append(i)

InitNumQueue()

def InitCheckPoint():
    global checkPoint
    checkPoint = []
    for r in range(SIZE - 1):
        idx = GetIndexFromRowCol(r, SIZE - 1)
        checkPoint.append(idx)

    for c in range(SIZE):
        idx = GetIndexFromRowCol(SIZE - 1, c)
        checkPoint.append(idx)

    print(checkPoint)

InitCheckPoint()

def CalcSum():
    sum = 0
    for i in range(1, SIZE * SIZE + 1):
        sum += i
    
    if sum % SIZE != 0:
        print("failed")
        return -1

    return sum // SIZE

SUM = CalcSum()

# 当前要放置的数字是否合法
def IsFillingValueValid(cur_index, val):
    global checkPoint, board
    if not cur_index in checkPoint:
        # 不是check_point的话就随便放
        return  True

    r, c = GetRowColFromIndex(cur_index)

    # 是check_point的话要进行合法性校验
    if c == SIZE - 1 and r != SIZE - 1:
        s = 0
        for i in range(SIZE - 1):
            s += board[r][i]
        if s + val == SUM:
            return True
    elif c == 0 and r == SIZE - 1:
        s1 = 0
        for i in range(SIZE - 1): 
            s1 += board[i][c]
        s2 = 0
        for i in range(1, SIZE):
            s2 += board[SIZE - 1 - i][i]
        if s1 + val == SUM and s2 + val == SUM:
            return True
    elif r == SIZE - 1 and c > 0 and c < SIZE - 1:
        s = 0
        for i in range(SIZE - 1):
            s += board[i][c]
        if s + val == SUM:
            return True
    elif c == SIZE - 1 and r == SIZE - 1:
        s1= 0
        for i in range(SIZE - 1):
            s1 += board[i][c]
        
        s2 = 0
        for i in range(SIZE - 1):
            s2 += board[r][i]

        s3 = 0
        for i in range(SIZE - 1):
            s3 += board[i][i]

        if s1 + val == SUM and s2 + val == SUM and s3 + val == SUM:
            return True

    return False

# 获取比输入数字大1且没有使用过的数字
def GetBiggerUnusedNum(num):
    while num < SIZE * SIZE:
        num += 1

        if num in numQueue:
           return num 
    
    # 没有找到符合要求的数字
    return -1

def CalcCheckPointNum(curIndex):
    global board, numQueue
    r, c = GetRowColFromIndex(curIndex)
    ret = -1
    # print("---->", r, c)
    if c == SIZE - 1 and r != SIZE - 1:
        cp = SUM
        for i in range(SIZE - 1):
            # print(cp, board[r][i])
            cp -= board[r][i] 
        if cp in numQueue:
            ret = cp
    elif c == 0 and r == SIZE - 1:
        cp = SUM
        for i in range(SIZE - 1):
            cp -= board[i][c]

        s = cp
        for i in range(1, SIZE):
            s += board[SIZE - 1 - i][i] 
        if cp in numQueue and s == SUM:
            ret = cp 
    elif r == SIZE - 1 and c > 0 and c < SIZE - 1:
        cp = SUM
        for i in range(SIZE - 1):
            cp -= board[i][c]

        if cp in numQueue:
            ret = cp
    elif r == SIZE - 1 and c == SIZE - 1:
        cp = SUM
        for i in range(SIZE - 1):
            cp -= board[i][c]
        
        s1 = cp
        for i in range(SIZE - 1):
            s1 += board[r][i]
        s2 = cp
        for i in range(SIZE - 1):
            s2 += board[i][i]

        if cp in numQueue and s1 == s2 == SUM:
            ret = cp
    return ret

def PutNum(curIndex, num):
    global board, numQueue
    r, c = GetRowColFromIndex(curIndex)
    board[r][c] = num
    resultStack.append((curIndex, num))
    numQueue.remove(num)

def main():
    global board, numQueue
    # 当前要填的格子
    curIndex = 0

    while len(numQueue) > 0:
        # 如果index in checkPoint，则自动补最后一个数字
        r, c = GetRowColFromIndex(curIndex)
        needRollBack = False
        if board[r][c] == 0:
            num = min(numQueue)
            if IsFillingValueValid(curIndex, num) == True:
                # 合法包括两种情况，一种是非checkpoint, 一种是合法的checkpoint
                PutNum(curIndex, num)
            else:
                # 否则计算checkpoint上究竟应该放数字几
                # 如果所需的数字不存在则触发回溯
                checkPointNum = CalcCheckPointNum(curIndex)
                if checkPointNum == -1:
                    needRollBack = True
                else:
                    PutNum(curIndex, checkPointNum)

            if needRollBack == True:
                # 不合法，进行回溯
                while True:
                    info = resultStack.pop()
                    rollBackIndex = info[0]
                    num = info[1]
                    rr, cc = GetRowColFromIndex(rollBackIndex)
                    numQueue.append(num)
                    nextNum = GetBiggerUnusedNum(num)
                    if nextNum != -1 and IsFillingValueValid(rollBackIndex, nextNum) == True:
                        PutNum(rollBackIndex, nextNum)
                        break
                    
                    # 如果nextNum == -1，则清理[rr][cc]继续回溯
                    board[rr][cc] = 0
                curIndex = rollBackIndex + 1
            else:
                curIndex += 1

    for r in range(SIZE):
        print(board[r])

start_time = time.time()
main()
total_time = time.time() - start_time
print(total_time)